package leetcode.editor.cn;

import java.util.Stack;

//[84]柱状图中最大的矩形
public class LargestRectangleInHistogram84 {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram84().new Solution();
        solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //栈里面 只会存储 左边的小值。左边界。
        public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length < 1) return 0;
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);//-1对应index，第一个位置是0，所以前一个位置是-1。计算宽度时方便。
            int maxArea = 0;
            for (int i = 0; i < heights.length; i++) {
                //栈里所有值 与 右边界 i 比较 。
                // >1 ? 当前有高度。这个 i 是右边界
                // 栈里面 只会存储 左边的小值。左边界。
                while (stack.size() > 1 && heights[stack.peek()] > heights[i]) {//当 stack 遇到右边界。弹出。
                    Integer curHeightMaxIndex = stack.pop();//当前最高的 index。
                    //重点，当前 右边界 i.
                    //i - stack.peek() - 1 》》》 右边界 - 左边界 -1
                    maxArea = Math.max(maxArea, heights[curHeightMaxIndex] * (i - stack.peek() - 1));//height * (right - left -1)
                }
                stack.push(i);
            }
            //while.前边的都比后边的小。 index 加入到。当 stack 遇到上边界。弹出。
            while (stack.size() > 1) {
                Integer popIndex = stack.pop();
                maxArea = Math.max(maxArea, heights[popIndex] * (heights.length - stack.peek() - 1));
            }
            return maxArea;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}